package hot_problems_100;
import java.util.ArrayList;
import java.util.List;

public class P9_0438 {
    /*
    * 求s中  p的异位串的起始位置集合
    * 两者长度 1~30000
    * */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()) return res;
        int[] char_nums = new int[26];
        int[] cur_char_nums =  new int[26];
        for(int i=0; i<p.length(); i++){
            char_nums[p.charAt(i)-'a'] ++;
            cur_char_nums[s.charAt(i)-'a'] ++;
        }
        boolean flag = true;
        for(int j=0; j<26; j++){
            if(cur_char_nums[j] == char_nums[j]) continue;
            else{
                flag = false;
                break;
            }
        }
        if(flag) res.add(0);

        for(int i=p.length(); i<s.length(); i++){
            char last_char = s.charAt(i-p.length());
            cur_char_nums[last_char-'a'] --;
            cur_char_nums[s.charAt(i)-'a'] ++;
            flag = true;
            for(int j=0; j<26; j++){
                if(cur_char_nums[j] == char_nums[j]) continue;
                else{
                    flag = false;
                    break;
                }
            }
            if(flag){
                res.add(i-p.length()+1);
            }
        }
        return res;
    }

    /*
    * 不再逐个对比键值，而是记录一个match_count
    * 当然，在本题中，这种运行耗时反而慢于上面，主要是数组哈希表太小了，经过优化后反而会更慢
    *
    * */
    public List<Integer> findAnagrams_better(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()) return res;
        int[] char_nums = new int[26];
        int[] cur_char_nums =  new int[26];
        for(int i=0; i<p.length(); i++){
            char_nums[p.charAt(i)-'a'] ++;
            cur_char_nums[s.charAt(i)-'a'] ++;
        }

        int match_count = 0;
        for(int j=0; j<26; j++){
            if(cur_char_nums[j] == char_nums[j]) match_count ++;
        }
        if(match_count==26) res.add(0);

        for(int i=p.length(); i<s.length(); i++){
            int index1 = s.charAt(i-p.length()) - 'a';
            int index2 = s.charAt(i) - 'a';

            if(cur_char_nums[index1]-1 == char_nums[index1]) match_count ++;
            else if(cur_char_nums[index1] == char_nums[index1]) match_count --;
            cur_char_nums[index1] --;

            if(cur_char_nums[index2]+1 == char_nums[index2]) match_count ++;
            else if(cur_char_nums[index2] == char_nums[index2]) match_count --;
            cur_char_nums[s.charAt(i)-'a'] ++;

            if(match_count == 26){
                res.add(i-p.length()+1);
            }
        }
        return res;
    }
}
